package fun.ticsmyc.question.stringQuestion;

import org.junit.Test;

/**
 *
 * 两种求回文子串的暴力方法
 * 解决奇偶问题的方法：
 * 1. 在字符间插特殊字符
 * 2. 奇数扩一次 偶数扩一次 选最长。
 * -----------------------------------
 * 其他方法：
 * 动态规划：记录从i-j子串是否是回文，如果是的话，只需要判断i-1和j+1是不是回文。 【不会写！】
 *
 * @author Ticsmyc
 * @package fun.ticsmyc.question.stringQuestion
 * @date 2020-03-08 22:28
 */
public class 最长回文子串_暴力 {

    public String longestPalindrome1(String s) {
        char[] str = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        for(int i=0; i<str.length ;++i){
            sb.append(str[i]);
            sb.append("#");
        }
      //  System.out.println(sb.toString());
        str =sb.toString().toCharArray();

        String res = "";

        for(int i =0 ; i<str.length ;++i){
            int left = i;
            int right =i;
            while(left-1 >=0 && right+1 <str.length  &&str[left-1]==str[right+1]){
                --left;
                ++right;
            }
            int length =(right -left +1)/2; //真实长度
           // System.out.println(i+"====="+length +"---" +left +"---"+right);
            if(length >res.length()){
                res = s.substring(left/2,right/2);
              //  System.out.println(res);
            }

        }
        return res;
    }

    public String longestPalindrome2(String s) {
        char[] str = s.toCharArray();

        String res = "";

        for(int i =0 ; i<str.length ;++i){
            int length1 = expand(str,i,i);
            int length2=expand(str,i-1,i);

            int length =Math.max(length1,length2);
            if(length >res.length()){
                if(length1>length2){
                    res = s.substring(i-length/2,i+length/2+1);
                }else{
                    res = s.substring(i-length/2,i+length/2);
                }

            }
        }
        return res;
    }

    public int expand(char[] str, int left ,int right){
        while(left>=0 && right <str.length  &&str[left]==str[right]){
            --left;
            ++right;
        }
        return right -left -1;
    }
    @Test
    public void test (){
        System.out.println(longestPalindrome2("abbd")) ;
    }

}
